package backtrack

import "fmt"

// 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
func combine(n int, k int) [][]int {
	var res [][]int
	
	backtrack([]int{},k,&res,1,n)

	return res
}

func backtrack(path []int, k int, res *[][]int,curIdx int,n int) {
	// 确定终止条件
	// if curIdx <1 || curIdx > n  {
	// 	return // 下标越界
	// }
	fmt.Println(path)
	if len(path) == k {  
		// 得到一个组合
		// copy入
		var copyPath []int
		for _,v := range path{copyPath = append(copyPath, v)}
		// copy(copyPath, *path)
		*res = append(*res, copyPath)
		fmt.Println(*res)
		return 
	}
	fmt.Println("line30",k,path,curIdx)
	// 搜索
	for i:=curIdx;i<=n;i++{   // 可以进行剪枝优化  
		path = append(path, i)  
		// fmt.Println(i)
		// curIdx 本次递归需要访问的数字
		backtrack(path,k,res,i+1,n)
		path = (path)[:len(path)-1]
	}
}